/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
//get rid of these includes later
#include <iostream>
#include <string>

using namespace std;

const int SETUP=0;

//helper functions
//determine leaf vs. nonleaf
bool isLeaf(PageId pid, PageFile pf);
void recInsert(const RecordId& rid,  PageFile& pf,
			   PageId& pid,		 int& key,
			   PageId& splitPid, int& splitKey);
bool recLocate(int searchKey, IndexCursor& cursor, PageId pid, PageFile pf);

/*
static void setLeaf(int spid, int pid)
{
	char buffer[PageFile::PAGE_SIZE];
	pf.read (spid, buffer);
	memcpy(buffer+(PageFile::PAGE_SIZE-2*sizeof(int)), &pid, sizeof(int));
	pf.write(spid, buffer);
}

static void getLeaf(int spid, int& pid)
{
	char buffer[PageFile::PAGE_SIZE];
	pf.read (spid, buffer);
	memcpy(pid, buffer+(PageFile::PAGE_SIZE-2*sizeof(int)),  sizeof(int));
	cout << "leaf id is: " <<endl; 
	
}
*/
void getEnd(int& end, PageFile pf)
{
	char buffer[PageFile::PAGE_SIZE];
	pf.read(SETUP, buffer);
	memcpy(&end, buffer+2*sizeof(int), sizeof(int));
}

void setEnd(int end, PageFile pf)
{
	char buffer[PageFile::PAGE_SIZE];
	pf.read(SETUP, buffer);
	memcpy(buffer+2*sizeof(int), &end, sizeof(int));
	cout << "setEnd: " << end << endl;
	pf.write(SETUP, &buffer);
}

void status(PageFile pf)
{
	char buffer[PageFile::PAGE_SIZE];
	int end;
	pf.read(SETUP, buffer);
	memcpy(&end, buffer, sizeof(int));
	cout << "key: " << end <<endl;
	memcpy(&end, buffer+sizeof(int), sizeof(int));
	cout << "root: " << end <<endl;
	memcpy(&end, buffer+2*sizeof(int), sizeof(int));
	cout << "end pid: " << end <<endl;
}

void leafStatus(PageId pid, PageFile pf)
{
	char buffer[PageFile::PAGE_SIZE];
	pf.read(pid, &buffer);
	int status;
	memcpy(&status, (buffer), sizeof(int));
	int leafcount=status;
	cout <<"Page Id: " << pid << endl;
	cout <<"leafcount: " << status <<endl;
	memcpy(&status, (buffer+sizeof(int)), sizeof(int));
	cout <<"isleaf: " << status <<endl;
	for (int i=0; i<(leafcount); i++)
	{
		memcpy(&status, (buffer+2*sizeof(int)+(3*sizeof(int)*i)), sizeof(int));
		cout <<"key "<< i << ": " << status <<endl;
		memcpy(&status, (buffer+3*sizeof(int)+(3*sizeof(int)*i)), sizeof(int));
		//cout << "page id: " << status <<endl;
		memcpy(&status, (buffer+4*sizeof(int)+(3*sizeof(int)*i)), sizeof(int));
		//cout << "slot id: " << status <<endl;
	}
	memcpy(&status, (buffer+PageFile::PAGE_SIZE-sizeof(int)), sizeof(int));
	cout << "next ptr: " << status <<endl;
}

void NonLeafStatus(PageId pid, PageFile pf)
{
	char buffer[PageFile::PAGE_SIZE];
	pf.read(pid, &buffer);
	int status;
	memcpy(&status, (buffer), sizeof(int));
	int leafcount=status;
	if (status==1337)
		return;
	cout <<"Page Id: " << pid << endl;
	cout <<"nonleafcount: " << status <<endl;
	memcpy(&status, (buffer+sizeof(int)), sizeof(int));
	cout <<"isleaf: " << status <<endl;
	for (int i=0; i<(leafcount); i++)
	{
		memcpy(&status, (buffer+3*sizeof(int)+(2*sizeof(int)*i)), sizeof(int));
		cout <<"key "<< i << ": " << status <<endl;
		memcpy(&status, (buffer+2*sizeof(int)+(2*sizeof(int)*i)), sizeof(int));
		cout << "page id: " << status <<endl;
		memcpy(&status, (buffer+4*sizeof(int)+(2*sizeof(int)*i)), sizeof(int));
		//cout << "slot id: " << status <<endl;
	}
	memcpy(&status, (buffer+PageFile::PAGE_SIZE-sizeof(int)), sizeof(int));
	cout << "last id: " << status <<endl;
}


//int depth=0;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	RC rc;
    rc=pf.open(indexname, mode);
	if (rc==0) 
	{
		//page id 0 contains data for 
		//setting up the index
		char buffer[PageFile::PAGE_SIZE];  
		pf.read(SETUP, &buffer);
		int key;
		memcpy(&key, &buffer, sizeof(int));
		cout << "key: " << key <<endl;
		if (key==1337) //only happens when the page is pre-written
		{
			cout << "pre written" <<endl;
			memcpy(&rootPid, (buffer+sizeof(int)), sizeof(int));
		}
		else 
		{
			rootPid=SETUP+1;
			key=1337;
			
			cout << "root pid: " << rootPid << endl;
			memcpy(buffer+sizeof(int), &rootPid, sizeof(int));
			memcpy(buffer, &key, sizeof(int));
			pf.write(SETUP, buffer);
			
			BTLeafNode ln;
			
			pf.read(rootPid, buffer);
			int count=0;
			memcpy(&buffer, &count, sizeof(int));
			pf.write(rootPid, &buffer);
			
			ln.read(rootPid, pf);
			int end=ln.getNextNodePtr();
			ln.setNextNodePtr(-1);
			
			ln.write(rootPid, pf);
			setEnd(rootPid, pf);
			
			
		}
		//pf.write(pid, &buffer);
		cout << "root pid: " << rootPid << endl;
		
		//string keyword (&buffer, PageFile::PAGE_SIZE);
		
	}
	return rc;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	RC rc;
	rc=pf.close();
    return rc;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	PageId splitPid=-1;
	int splitKey=-1;
	int newRoot=-1;
	recInsert(rid, pf, rootPid,	key, splitPid,  splitKey);
	
    if (splitKey!=-1)//the root split so a new root needs to be initialized
	{
		BTNonLeafNode nln;
		cout << "old root pid: " << rootPid << endl;
		cout << "split pid: " << splitPid << endl;
		nln.initializeRoot(rootPid, splitKey, splitPid);
		getEnd(rootPid, pf);
		rootPid++; 
		cout << "root pid set to: " << rootPid << endl;
		
		char buffer[PageFile::PAGE_SIZE];
		pf.read(SETUP, buffer);
		memcpy(buffer+sizeof(int), &rootPid, sizeof(int));
		pf.write(SETUP, buffer);
		
		nln.write(rootPid, pf);
		NonLeafStatus(rootPid, pf);
		setEnd(rootPid, pf);
	}
	//NonLeafStatus(rootPid, pf);
	
	if (key==3895 || key==3411)
	{
		for (int i=0; i<pf.endPid(); i++)
		{
			if (isLeaf(i, pf))
			{
				leafStatus(i, pf);
			}
			else {
			NonLeafStatus(i, pf);
			}

		}
	}
	
	//leafStatus(rootPid, pf);
	
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	
	if (recLocate(searchKey, cursor, rootPid, pf))
	{
		return 0;
	}
	else
	{
		cout << "error in locate" <<endl;
		return -1;
	}

}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode ln;
	ln.read(cursor.pid, pf);
	ln.readEntry(cursor.eid, key, rid);
	cursor.eid++;
	if(cursor.eid==ln.getKeyCount())
	{
		cursor.pid=ln.getNextNodePtr();
		cursor.eid=0;
	}
    return 0;
}






bool isLeaf(PageId pid, PageFile pf)
{
	int isleaf;
	char buffer[PageFile::PAGE_SIZE];
	pf.read(pid, buffer);
	memcpy(&isleaf, (buffer+sizeof(int)), sizeof(int)); //copies if it is a leaf
	if (isleaf==42)
	{
		return true;
	}
	return false;
}

void recInsert(const RecordId& rid,  PageFile& pf,
			   PageId& pid,		 int& key,
			   PageId& splitPid, int& splitKey)
{
	//bool isleaf;
	char* buffer[PageFile::PAGE_SIZE];
	//cout << "is leaf read successful" <<endl;
	
	pf.read(pid, &buffer);
	//memcpy(&isleaf, buffer+sizeof(int), sizeof(bool)); //copies if it is a leaf

	//cout << "is leaf read successful: " << s <<endl;
	
	//in case of split
	bool wasSplit=false;
	BTLeafNode ln2;
	int siblingKey=-1;
	
	
	
	if(isLeaf(pid, pf))
	{
		BTLeafNode ln;
		ln.read(pid, pf);
		
		
		if (ln.getKeyCount()+1==LEAF_MAX)
		{
			
			wasSplit=true;
			cout << "attempting insert and split" << endl; 
			ln.insertAndSplit(key, rid, ln2, siblingKey);
			cout << "insert and split completed" <<endl; 
			splitKey=siblingKey;
			
			
			getEnd(splitPid, pf); //set new split pid and key
			cout << "pre increment end: " << splitPid << endl; 
			splitPid++;
			setEnd(splitPid, pf);
			cout << "pf end: " << splitPid <<endl;
			int endptr = ln.getNextNodePtr();
			ln.setNextNodePtr(splitPid);
			ln2.setNextNodePtr(endptr);
			ln2.write(splitPid, pf);
			
		}
		else
		{
			ln.insert(key, rid);
			splitKey=-1;
		}
		ln.write(pid, pf);
		
	}
	else
	{
		//current node is non leaf
		BTNonLeafNode nln;
		nln.read(pid, pf);
		
		//search for the next node to insert into
		PageId recPid;
		nln.locateChildPtr(key, recPid);
		
		//try to insert into the next node (recursive call)
		recInsert(rid, pf, recPid, key, splitPid, splitKey);
		
		if (splitKey==-1)
		{
			if (nln.getKeyCount()==NON_LEAF_MAX)
			{/*
				BTNonLeafNode nln2;
				int siblingKey;
				cout << "attempting non leaf split" <<endl;
				nln.insertAndSplit(key, pid, nln2, siblingKey);
				splitPid=pf.endPid();
				nln2.write(splitPid, pf);
			  */
			}
			else
			{
				//nln.insert(key, pid);
			}
		}
		else // the previous node was split and now an insertion must be performed
		{
			cout <<"split key: " << splitKey <<endl;
			if (nln.getKeyCount()+1==NON_LEAF_MAX)
			{
				//the current node will need to be split 
				//and therefore return two keys and pids
				BTNonLeafNode nln2;
				int siblingKey;
				nln.insertAndSplit(splitKey, splitPid, nln2, siblingKey);
				
				//determine where to put the second key
				if (siblingKey<splitKey)
				{
					nln.insert(splitKey, splitPid);
				}
				else 
				{
					nln2.insert(splitKey, splitPid);
				}
				
				splitKey=siblingKey;
				splitPid=pf.endPid(); //set new split pid and key
				nln2.write(splitPid, pf);
				
			}
			else
			{
				cout << "non leaf insert" << endl;
				nln.insert(splitKey, splitPid);
				nln.write(pid, pf);
				
				splitKey=-1;
				splitPid=-1; //reset these values so when it the next level
							 //up only performs one insert.
			}
		}
		nln.write(pid, pf); //save nln
	}
}

bool recLocate(int searchKey, IndexCursor& cursor, PageId pid, PageFile pf)
{
	cout << "search page: " << pid <<endl; 
	if(isLeaf(pid, pf))
	{
		BTLeafNode ln;
		ln.read(pid, pf);
		int eid;
		if(ln.locate(searchKey, eid)==0)
		{
			cursor.eid=eid;
			cursor.pid=pid;
			return true;
		}
		else 
		{
			return false;
		}
	}
	else
	{
		PageId recPid;
		BTNonLeafNode nln;
		nln.read(pid, pf);
		nln.locateChildPtr(searchKey, recPid);
		recLocate(searchKey, cursor, recPid, pf);
	}

	
}





/*
code that was taken from the first draft of insert
 
bool isleaf;
RC rc;
char* buffer[PageFile::PAGE_SIZE];
if (depth==0)
{ 
	bool isleaf;
	RC rc;
	char* buffer[PageFile::PAGE_SIZE];
	pf.read(rootPid, buffer);
	memcpy(&isleaf, buffer+sizeof(int), sizeof(bool)); //copies if it is a leaf
}
else
{
	
	
}

if(!isleaf)
{
	insert(key, rid);
	
	/*
	 BTNonLeafNode nln;
	 nln.read(rootPid, pf);
	 PageId pid;
	 while (!isleaf)
	 {
	 nln.locateChildPtr(key, pid);
	 memcpy(&isleaf, buffer+sizeof(int), sizeof(bool));
	 }
	 
	 BTLeafNode ln;
	 ln.read(rootPid, pf);
	 if (ln.getKeyCount()==LEAF_MAX)
	 {
	 BTLeafNode ln2;
	 int siblingKey;
	 ln.insertAndSplit(key, rid, ln2, siblingKey);
	 }
	 else
	 {
	 ln.insert(key, rid);
	 }
	
	
	//follow to next node down until you reach a leaf node (recursive)
}
else 
{
	
	BTLeafNode ln;
	ln.read(rootPid, pf);
	if (ln.getKeyCount()==LEAF_MAX)
	{
		BTLeafNode ln2;
		int siblingKey;
		ln.insertAndSplit(key, rid, ln2, siblingKey);
	}
	else
	{
		ln.insert(key, rid);
	}
}

*/

